package com.example.demo.sort;

/**
 * 快速排序
 *
 * @author wangadmin
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] sortArray = SortContent.sortArray;
        QuickSort.quickSort(sortArray, 0, sortArray.length - 1);
    }

    /**
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int l = low;
        int r = high;

        //pivot 为比较基准位数 这默认取最右边的
        int pivot = arr[high];

        while (l < r) {
            //依次往右递增
            while (arr[l] <= pivot && l < r) {
                l++;
            }
            //依次往左递减
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            //如果满足条件则交换
            if (l < r) {
                int t = arr[l];
                arr[l] = arr[r];
                arr[r] = t;
            }
        }

        // pivot 基准数和比较的数字交换位置
        if (l == r) {
            arr[high] = arr[l];
            arr[l] = pivot;
        }

        //递归调用左半数组
        quickSort(arr, low, r - 1);
        //递归调用右半数组
        quickSort(arr, r + 1, high);
    }


}
